//混合背包
#include <iostream>
using namespace std;
const int MAXN=30;
const int MAXV=200;
int v,n;
int w[MAXN+1],c[MAXN+1],p[MAXN+1];
int maxc[MAXV+1];

int main(){
    cin>>v>>n;
    for(int i=1;i<=n;i++) cin>>w[i]>>c[i]>>p[i];

    /*for(int i=1;i<=n;i++) {
        if (p[i]==0) p[i]=v/w[i];
        for(int k=1;k<=p[i];k++)
            for(int m=v;m>=w[i];m--)
                maxc[m]=max(maxc[m],maxc[m-w[i]]+c[i]);

    }*/
    //二进制优化
    for(int i=1;i<=n;i++) {
        if (p[i]==0) p[i]=v/w[i];
        for(int k=0,q=1;q<=p[i];k++,q=1<<k){
            if (q*2>p[i]) q=p[i]-q+1;
            for(int m=v;m>=q*w[i];m--)
                maxc[m]=max(maxc[m],maxc[m-q*w[i]]+q*c[i]);
        }   
    }
    cout<<maxc[v];
}